Analysis of the Sufficient Path Elimination Window for the Maximum-Likelihood Sequential-Search Decoding Algorithm for Binary Convolutional Codes

摘要

A common problem on sequential-type decoding is that at the signal-to-noiseratio (SNR) below the one corresponding to the cutoff rate, the averagedecoding complexity per information bit and the required stack size growrapidly with the information length. In order to alleviate the problem in themaximum-likelihood sequential decoding algorithm (MLSDA), we propose todirectly eliminate the top path whose end node is $\Delta$-trellis-level priorto the farthest one among all nodes that have been expanded thus far by thesequential search. Following random coding argument, we analyze theearly-elimination window $\Delta$ that results in negligible performancedegradation for the MLSDA. Our analytical results indicate that the requiredearly elimination window for negligible performance degradation is just twiceof the constraint length for rate one-half convolutional codes. For rateone-third convolutional codes, the required early-elimination window evenreduces to the constraint length. The suggestive theoretical level thresholdsalmost coincide with the simulation results. As a consequence of the smallearly-elimination window required for near maximum-likelihood performance, theMLSDA with early-elimination modification rules out considerable computationalburdens, as well as memory requirement, by directly eliminating a big number ofthe top paths, which makes the MLSDA with early elimination very suitable forapplications that dictate a low-complexity software implementation with nearmaximum-likelihood performance.